A garbled circuit is a method Proposed by Andy Yao in 1986 for secure multiparty computation. This is a two party protocol. This protocol is only secure against an adversary from the Honest-but-curious adversary model. In Yao's protocol, one party (called the circuit creator) takes a binary circuit C, and produces a so-called Garbled binary Circuit GC, which is a form of encrypted representation of the circuit.
In particular every wire in the circuit is given two garbled labels, which are each a cryptographic key. One garbled label corresponds to the zero signal on the wire, and the other corresponds to the output signal. Each gate in the circuit is replaced by an encryption table, called a garbled gate. The table is such that knowledge of garbled labels corresponding to the input wire signals, allows one to compute the corresponding label of the output wire signal. The set of all such garbled gates is called the Garbled binary Circuit GC.
The GC is sent to the second party along with the garbled labels corresponding to the inputs of the first party, and a table mapping garbled output labels to actual output values. The second party (called the circuit evaluator) obtains the garbled labels according to its own inputs by performing an Oblivious Transfer (OT) protocol with the circuit creator. The evaluating party can now evaluate the garbled circuit, and hence obtain the output of the binary circuit on the input provided by the two parties (using the table of garbled output labels). Since the inputs are only provided as garbled labels, this is done without the evaluating party learning the inputs of the first party. Standard modifications, known in the art, allow both parties to obtain different outputs (i.e. compute different functions on the joint inputs).
As described above we only achieve a passively secure protocol; i.e. the protocol is not secure if one of the parties deliberately deviates from the protocol. Passive security is a very weak form of security. Ideally one requires a protocol which is actively secure. An actively secure protocol is still secure (in the sense of input privacy and output correctness) even if one of the participating parties deviates from the protocol in an arbitrary manner.
To make the Yao protocol actively secure one usually needs a lot more complex operations. The standard method in the literature to achieve active security is to use a form of cut-and-choose. This is explained in various papers such as Lindell and Pinkas 2015. However, using cut-and-choose is very expensive in terms of the additional computational costs. Another method to achieve active security is to increase the number of computing parties from two to three; we can achieve active security at very little extra cost if we assume only one of the three servers is corrupted at any one time. A variant for producing such a protocol has been given by Mohassel et al. However, it is not suited for where one party is a bandwidth constrained mobile device, due to the high bandwidth constrains imposed on the two parties.